A server system is a processing system utilized to store and retrieve data on behalf of one or more clients. A server system operates on behalf of the one or more client systems to store and manage shared data in a set of mass storage devices, such as magnetic or optical storage-based disks or tapes. A server system may include an operating system that implements a file system for storing and organizing computer files and the data they contain. A file system is any organization of data in a structured manner, which is typically organized as a hierarchical set of stored files, directories and/or other types of data containers. Data stored by a server system may be stored in the form of multiple blocks that each contains data. A block is the unit used by a file system in a server system to manipulate and transfer data. A typical file system may contain thousands (or even hundreds of thousands) of directories. Related files are stored in the same directory. A directory contained inside another directory is called a subdirectory. For efficient data processing of a data structure, a directory can be represented as a tree having a plurality of nodes.
With reference now to FIG. 4, an exemplary directory structure 400 stored on a server system is illustrated. Those skilled in the art would understand that FIG. 4 is described herein to briefly introduce a concept of a file directory structure. FIG. 4 will be described in more detail later to describe various embodiments of the invention. A node (e.g., a data container, directory, or a subdirectory) within a directory structure has zero or more child nodes. A node that has a child is called a parent node. A node typically has at most one parent, except for the root node, which does not have a parent node. A parent node is associated with one or more links (such as links l1 and l2), which point to its child nodes. These links indicate a logical association between the parent nodes and the child nodes. For example, node X is a root node of the data structure 400 and it is a parent of child nodes A and B. Being the topmost node, the root node X does not have parents. In directory structure 400, root node X and nodes A, B, D, E, and G are directory nodes. Nodes C, F, H, and I are leaf nodes (e.g., nodes at the bottom level of the data structure). In the directory structure 400, G and H are data containers within directory D. H and I are data containers within directory E, and F is a data container within directory B. Each node, whether it is a directory node or a data container node, has an inode number associated with it. Ancestors of a node include all parents, grandparents, etc. An inode is a data structure storing information about a data container, such as, for example, an identifier of the device where the inode resides, locking information, a type of the data container, the number of links to the data container, the owner's user and group identification, the number of bytes in the data container, access and modification times, the time the inode itself was last modified, as well as other data. An inode number refers to a pointer of an inode data structure, and thus its associated data container. An inode number is used to look up an entry in the inode data structure. A root inode is an entry point used during processing of the node tree, and is located at a readily identified location on a storage device, e.g., disk.
Finding out all ancestral directory associations (i.e., direct or indirect parent nodes) of a data container given the data container identifier has been a common problem in implementing some operations of a computer system, such as performing directory notification to a client, maintaining directory-based quotas, and other such operations.
Directory notification service is a mechanism by which a client system can register with a file system for notifications about accesses, changes, or modifications to a file within a particular directory. For example, an application resident on a client system can register with the server system by exposing Application Programming Interfaces (API) to the file system. Server system may maintain mappings between directories being watched for modifications and applications that are registered to receive updates regarding modifications to directories. An application can specify a set of conditions that trigger notification, such as changes to data container names, directory names, attributes, data container size, time of last write, and security. Notification service typically suffers from severe performance penalties. Currently, a Network File System (NFS) client can access a particular data container at a server system using a data container handler that typically encapsulates the inode number of the data container. However, in order to determine all parent nodes of the data container (and thus its path name to the root node), each inode data structure, which is associated with a data container and thus maintains a pointer to its parent, needs to be accessed. Once the immediate parent node is identified, the next immediate parent node needs to be determined (again by accessing a corresponding inode data structure for that node that identifies its parent) and so forth until the complete path name of the node up to the root node is established. Accessing inode data structures in order to retrieve a pointer may require multiple accesses to storage devices where the inode data structures reside. When the path of a data container is determined, the server system compares the path to the names of the directories for which notifications are requested by the client system. Such a comparison may be performed by using, for example, a text based match. If a match is found, the server system issues notifications to clients registered for notifications. Thus, identifying a complete path name of a data container that was accessed and modified may involve multiple accesses to storage devices, which in turn, leads to compromised performance.
Maintaining directory quota by a server system involves setting a data container and block (storage) usage limit on a per directory basis, e.g., a limit on the usage by a particular user at a client system or a group for data containers files and sub-directories that reside under a given directory. Thus, if a data container is modified by a client system (e.g., file system allocates more data blocks or frees data blocks) and a directory that includes a particular data container has a quota which cannot be exceeded, client systems need to be notified by the server system about the changes. Again, finding parent directories of a data container or directory by a server system may involve finding an upward path of the modified data container or directory in the file system all the way up to the root node. Upward traversal can be costly because it involves accessing by the file system one node at a time in a directory structure. Every node access results in a new access to a storage device in order to retrieve a pointer to a parent node. Moreover, maintaining hard links by the file system make the above tasks even more difficult. A node in a file system is said to have a hard link if it has more than one parent directory so that more than one parent node has a pointer to the node. As such, hard links lead to more than one way to reach to the node in the directory tree from the root, and thus may potentially lead to multiple accesses of data structures associated with a node (e.g., inode data structures).
Accordingly, what is a needed is a mechanism that performs directory notification to a client, maintains directory-based quota and other such operations more efficiently.